In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Let us consider a text consisting of words numbered from
to
. We represent any of its
decompositions into
lines by a sequence of numbers
,
such that the words with numbers from
to
are in the first line, the words with numbers from
to
are in the second line, and so on, and finally, the words with numbers from
to
are in the last,
-th line.
Each word has a certain length (measured in the number of characters). Let denote
the length of the word no.
. Furthermore, every two subsequent words in a line are separated by a
space of width of a single character. By length of the line we denote the sum of lengths of the words
in this line, increased by the number of spaces between them. Let
denote the length of the
line no.
. I.e., if the line no.
contains the words with numbers from
to
inclusive, its length
is:
As an example, let us consider a text consisting of words of lengths
,
,
and
, respectively, and
its decomposition
into
lines. Then the length of the first line is
, second -
, and third
-
:
XXXX (1st line)
XXX XX (2nd line)
XXXXX (3rd line)
We shall refer to the number
as the coefficient of aestheticism of a decomposition of the given text into lines. Particularly, if
the decomposition has only one line, its coefficient of aestheticism is
.
Needles to say, the smaller the coefficient, the more aesthetical the decomposition. We shall
consider only these decompositions that have no line whose length exceeds some constant . Of all
such decompositions of a given text into any number of lines we seek the one most aesthetical, i.e.
the one with the smallest coefficient of aestheticism. The aforementioned examplary decomposition's
coefficient is
, and that is exactly the minimum coefficient of aestheticism for
and
.
Write a programme that:
The first line of the standard input contains the numbers and
,
,
, separated by a single space. The second, last line of the standard input contains
integers, denoting
the lengths of subsequent words,
for
, separated by single spaces.
The first and only line of the standard output should contain exactly one integer: the minimum
coefficient of aestheticism for those decompositions, whose every line's length does not exceed .
For the input data:
6 4 4 3 2 5
the correct result is:
3
while for the following input data:
4 2 1 2
the correct result is:
0
Task author: Bartosz Walczak.